/*
** xarray.template.h
** vim: ft=c ts=4 sw=4 et
**
** Template definition for expanding arrays.  The initial_size argument
** must be at least 1.  The storage used can be reclaimed with free().
**
** Define XARRAY_NAME to specify the type name (mandatory).
** Define
**      XARRAY_INIT
**      XARRAY_PUSH
**      XARRAY_POP
**      XARRAY_UNSAFE_SWAP
**      XARRAY_SWAP
**      XARRAY_APPEND
** as function names.
** Define XARRAY_ITEM_TYPE to specify the element type (default 'void *').
** Define XARRAY_INIT_SIZE to specify the initial size (default '8').
** Define XARRAY_H to output the declarations.
** Define XARRAY_C to output the implementation.
** (If neither is defined then you get both.)
** Define XARRAY_MALLOC and XARRAY_FREE to specify malloc and free functions
** (default is 'malloc' and 'free').
**
** These symols are 'undef'ed at the end of this file.
*/

#if !defined(XARRAY_NAME)
#error "xarray.template.h: you must define XARRAY_NAME"
#endif

#if !defined(XARRAY_INIT)
#error "xarray.template.h: you must define XARRAY_INIT."
#endif

#if !defined(XARRAY_PUSH)
#error "xarray.template.h: you must define XARRAY_PUSH."
#endif

#if !defined(XARRAY_POP)
#error "xarray.template.h: you must define XARRAY_POP."
#endif

#if !defined(XARRAY_UNSAFE_SWAP)
#error "xarray.template.h: you must define XARRAY_UNSAFE_SWAP."
#endif

#if !defined(XARRAY_SWAP)
#error "xarray.template.h: you must define XARRAY_SWAP."
#endif

#if !defined(XARRAY_APPEND)
#error "xarray.template.h: you must define XARRAY_APPEND."
#endif

#if !defined(XARRAY_H) && !defined(XARRAY_C)
#define XARRAY_H
#define XARRAY_C
#endif

#if !defined(XARRAY_TYPE)
#define XARRAY_TYPE void *
#endif

#if !defined(XARRAY_INIT_SIZE)
#define XARRAY_INIT_SIZE 8
#endif

#if XARRAY_INIT_SIZE < 1
#error "xarray.template.h: XARRAY_INIT_SIZE must be positive"
#endif

#if !defined(XARRAY_MALLOC)
#define XARRAY_MALLOC malloc
#endif

#if !defined(XARRAY_FREE)
#define XARRAY_FREE free
#endif

#define _XARRAY_(suffix) XARRAY_NAME _ suffix
#define _XARRAY_Q(name) #name



#ifdef XARRAY_H

struct XARRAY_NAME {
        /* Items item[0]..item[size-1] are valid. */
    int size;
        /* The maximum size of the array before resizing is needed. */
    int max_size;
        /* The item array is allocated to have max_size cells. */
    XARRAY_ITEM_TYPE item[1];
};
typedef struct XARRAY_NAME XARRAY_NAME;

    /*
    ** Initialise a new, empty, xarray.
    */
XARRAY_NAME *
XARRAY_INIT();

    /*
    ** Add an item to the end of an xarray (may resize the array).
    */
XARRAY_NAME *
XARRAY_PUSH(XARRAY_NAME *a, XARRAY_ITEM_TYPE x);

    /*
    ** Remove the last item from the xarray (aborts with an error
    ** if the xarray is empty.
    */
XARRAY_ITEM_TYPE
XARRAY_POP(XARRAY_NAME *a);

    /*
    ** Swap two elements of an xarray (the unsafe version does not
    ** check the indices for validity, the other version aborts with
    ** an error if the indices are out of range).
    */
void
XARRAY_UNSAFE_SWAP(XARRAY_NAME *a, int i, int j);
void
XARRAY_SWAP(XARRAY_NAME *a, int i, int j);

    /*
    ** Concatenate the second xarray on to the first.
    */
XARRAY_NAME *
XARRAY_APPEND(XARRAY_NAME *a, XARRAY_NAME *b);

#endif /* XARRAY_H */



#ifdef XARRAY_C

XARRAY_NAME *
XARRAY_INIT()
{
    XARRAY_NAME *a =
        (XARRAY_NAME *)XARRAY_MALLOC(
            sizeof(XARRAY_NAME) +
            (XARRAY_INIT_SIZE - 1) * sizeof(XARRAY_ITEM_TYPE)
        );
    if (a == NULL) {
        fprintf(stderr, "%s: call to %s returned NULL.\n",
            _XARRAY_Q(XARRAY_INIT), _XARRAY_Q(XARRAY_MALLOC));
        exit(1);
    }
    a->size = 0;
    a->max_size = XARRAY_INIT_SIZE;
    return a;
}

XARRAY_NAME *
XARRAY_PUSH(XARRAY_NAME *a, XARRAY_ITEM_TYPE x)
{
    unsigned int size = a->size;
    unsigned int max_size = a->max_size;

    if (size == max_size) {
        int i;
        int new_max_size = max_size + max_size;
        XARRAY_NAME *old_a = a;
        XARRAY_NAME *new_a =
            (XARRAY_NAME *)XARRAY_MALLOC(
                sizeof(XARRAY_NAME) +
                (new_max_size - 1) * sizeof(XARRAY_ITEM_TYPE)
            );

        if (new_a == NULL) {
            fprintf(stderr, "%s: call to %s returned NULL.\n",
                _XARRAY_Q(XARRAY_PUSH), _XARRAY_Q(XARRAY_MALLOC));
            exit(1);
        }

        new_a->size = size;
        new_a->max_size = new_max_size;

        for (i = 0; i < size; i++) {
            new_a->item[i] = old_a->item[i];
        }

        XARRAY_FREE(old_a);

        a = new_a;
    }

    a->item[size] = x;
    a->size++;

    return a;
}

XARRAY_ITEM_TYPE
XARRAY_POP(XARRAY_NAME *a)
{
    if (a->size == 0) {
        fprintf(stderr, "%s: empty %s.\n",
            _XARRAY_Q(XARRAY_POP), _XARRAY_Q(XARRAY_NAME));
        exit(1);
    }

    a->size--;

    return a->item[a->size];
}

void
XARRAY_UNSAFE_SWAP(XARRAY_NAME *a, int i, int j)
{
    XARRAY_ITEM_TYPE tmp = a->item[i];
    a->item[i] = a->item[j];
    a->item[j] = tmp;
}

void
XARRAY_SWAP(XARRAY_NAME *a, int i, int j)
{
    int size = a->size;

    if (0 <= i && i < size && 0 <= j && j < size) {
        XARRAY_UNSAFE_SWAP(a, i, j);
    } else {
        fprintf(stderr, "%s: index out of range.\n",
            _XARRAY_Q(XARRAY_SWAP));
        exit(1);
    }
}

XARRAY_NAME *
XARRAY_APPEND(XARRAY_NAME *a, XARRAY_NAME *b)
{
    /*
    ** This is asymptotically efficient :-)
    */
    int i;

    for (i = 0; i < b->size; i++) {
        a = XARRAY_PUSH(a, b->item[i]);
    }

    return a;
}

#endif /* XARRAY_C */

#undef _XARRAY_
#undef _XARRAY_Q
#undef XARRAY_NAME
#undef XARRAY_PUSH
#undef XARRAY_POP
#undef XARRAY_UNSAFE_SWAP
#undef XARRAY_SWAP
#undef XARRAY_APPEND
#undef XARRAY_ITEM_TYPE
#undef XARRAY_INIT_SIZE
#undef XARRAY_H
#undef XARRAY_C
#undef XARRAY_MALLOC
#undef XARRAY_FREE

